import java.util.*;
class Solution{

    /**
     * 问题：子区间0和1个数相同，求最长的区间
     * 链接：https://leetcode.cn/problems/contiguous-array/
     * 时间复杂度：O(N);
     * 空间复杂度：O(N);
     */
    public int findMaxLength(int[] nums) {
        //将数组中的0变为-1
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) nums[i] = -1;
        }

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Set<Integer> set = new TreeSet<Integer>();
        map.put(0, 0);
        //求前缀和并统计
        int sum = 0, ret = 0;
        for (int i = 0; i < nums.length; i++) {
            //前缀和
            sum += nums[i];
            int t = map.getOrDefault(sum, -1);
            if (t != -1) {
                ret = Math.max(ret, i + 1 - t);
            }
            //更新
            if (sum != 0 && !set.contains(sum))
                map.put(sum, i + 1);

            set.add(sum);
        }
        return ret;
    }



/**
 * 问题：---
 * 链接：---https://leetcode.cn/problems/contiguous-array/
 * 时间复杂度：O(N);
 * 空间复杂度：O(N);
 */
    public static int findMaxLength1(int[] nums) {


        Map<Integer,Integer> map = new HashMap<Integer,Integer>();

        map.put(0,-1);

        int sum = 0,ret = 0;
        for(int i = 0;i < nums.length;i++){
            //前缀和
            sum += nums[i] == 0 ? -1 : nums[i];
            if(map.containsKey(sum))
                ret = Math.max(ret,i - map.get(sum));
                //更新
            else
                map.put(sum,i);
        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println(Solution.findMaxLength1(new int[]{0, 1}));
    }

    /**
     * 问题：求区域和
     * 链接：https://leetcode.cn/problems/matrix-block-sum/
     * 时间复杂度：O(n*m);
     * 空间复杂度：O(n*m);
     */

    public int[][] matrixBlockSum(int[][] mat, int k) {
        //预处理阶段
        int m = mat.length;
        int n = mat[0].length;

        int[][] dp = new int[m + 1][n + 1];

        //初始化dp表
        for(int i = 1;i < m + 1;i++){
            for(int j = 1;j < n + 1;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i - 1][j -1];
            }
        }

        //创建anser数组
        int[][] answer = new int[m][n];

        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                int x1 = Math.max(0,i - k) + 1;
                int y1 = Math.max(0,j - k) + 1;
                int x2 = Math.min(m - 1,i + k) + 1;
                int y2 = Math.min(n - 1,j + k) + 1;

                //获取区域和
                answer[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 -1] + dp[x1 - 1][y1 - 1];
            }
        }

        return answer;
    }

    /**
     * 问题：
     * 链接：
     * 时间复杂度：O();
     * 空间复杂度：O();
     */

}